Maximum Square || Maximum Rectangle

发表于

Maximal Square

Question

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1
2
3
4
1 0 1 0 0
1 0 **1 1** 1
1 1 **1 1** 1
1 0 0 1 0

Return 4.

Analysis

LeetCode Discuss

  • 定义dp数组的维数(m+1)*(n+1)可以控制边界问题
  • dp[i][j]用于记录以当前点为正方形右下角顶点的正方形的最长边长
  • 当我们判断以某个点为正方形右下角时最大的正方形时，那它的上方，左方和左上方三个点也一定是某个正方形的右下角，否则该点为右下角的正方形最大就是它自己了。这是定性的判断，那具体的最大正方形边长呢？我们知道，该点为右下角的正方形的最大边长，最多比它的上方，左方和左上方为右下角的正方形的边长多1，最好的情况是是它的上方，左方和左上方为右下角的正方形的大小都一样的，这样加上该点就可以构成一个更大的正方形。但如果它的上方，左方和左上方为右下角的正方形的大小不一样，合起来就会缺了某个角落，这时候只能取那三个正方形中最小的正方形的边长加1了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix==null||matrix.length==0)    return 0;
        int m=matrix.length,n=matrix[0].length,result=0;
        int[][] dp=new int[m+1][n+1];
        
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(matrix[i-1][j-1]=='1'){
                    dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i-1][j-1]),dp[i][j-1])+1;
                    result=Math.max(dp[i][j],result);
                }
            }
        }
        return result*result;
    }
}

Maximal Rectangle

Question

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

For example, given the following matrix:

1
2
3
4
1 0 1 0 0
1 0 **1 1 1**
1 1 **1 1 1**
1 0 0 1 0

Return 6

Analysis

LeetCode Discuss

Another Method

利用height,left,right三个数组来记录当前行内可形成最大矩形的高度、左边界和右边界。

  • height表示当前列内连续的1的个数，即高度
  • right和left注意需要在赋值的时候righttmp-1或者lefttmp+1， 这样能保证在计算的时候right-left正好是矩形的边长

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix==null||matrix.length==0)  return 0;
        int m=matrix.length,n=matrix[0].length,res=0;
        int[] left=new int[n];
        int[] right=new int[n];
        Arrays.fill(right,n);
        int[] height=new int[n];
        for(int i=0;i<m;i++){
            int lefttmp=0;
            int righttmp=n;
            //Compute height
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1')   height[j]+=1;
                else    height[j]=0;
            }
            //From left to right compute left
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1')   left[j]=Math.max(left[j],lefttmp);
                else{
                    left[j]=0;
                    lefttmp=j+1;
                }
            }
            //From right to left compute right
            for(int j=n-1;j>=0;j--){
                if(matrix[i][j]=='1')   right[j]=Math.min(right[j],righttmp);
                else{
                    right[j]=n;
                    righttmp=j;
                }
            }
            for(int j=0;j<n;j++){
                res=Math.max(res,(right[j]-left[j])*height[j]);
            }
        }
        return res;
    }
}